package huadi.algorithm.sort;

/**
 * MergeSort 归并排序
 * 
 * @author Huadi
 */
public class MergeSort {
	public static void sort(int[] array) {
		sortInside(array, 0, array.length - 1);
	}

	private static void sortInside(int[] array, int beginIndex, int endIndex) {
		if (beginIndex == endIndex)
			return;
		Integer mid = (beginIndex + endIndex) >> 1;
		sortInside(array, beginIndex, mid);
		sortInside(array, mid + 1, endIndex);
		merge(array, beginIndex, mid, endIndex);
	}

	private static void merge(int[] array, int beginIndex, int midIndex,
			int endIndex) {
		int[] tempArray = new int[endIndex - beginIndex + 1];
		for (int i = 0; i < tempArray.length; i++) {
			tempArray[i] = array[beginIndex + i];
		}

		int i = 0;
		int tempMid = midIndex - beginIndex, tempEnd = endIndex - beginIndex;
		int firstPointer = 0, secondPointer = tempMid + 1;
		while (firstPointer <= tempMid && secondPointer <= tempEnd) {
			if (tempArray[firstPointer] <= tempArray[secondPointer]) {
				array[beginIndex + i++] = tempArray[firstPointer++];
			} else {
				array[beginIndex + i++] = tempArray[secondPointer++];
			}
		}
		if (firstPointer > tempMid) {
			while (secondPointer <= tempEnd) {
				array[beginIndex + i++] = tempArray[secondPointer++];
			}
		}
		if (secondPointer > tempEnd)
			while (firstPointer <= tempMid) {
				array[beginIndex + i++] = tempArray[firstPointer++];
			}
		return;
	}
}
